public class FirstMissingPositive {
    // leetcode 缺失的第一个正数
    // https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
    public int firstMissingPositive(int[] nums) {
        // 通过分析我们可以发现，可能的结果在[1,n+1]范围内，
        // 所以可以通过原地hash的方法来将执行位置的元素设置为负数
        int n = nums.length;
        // 先遍历一遍数组，将[1,n+1]之外的数字设置为不影响结果的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) nums[i] = n+1;
        }
        // 原地hash将存在的元素对应的下标的元素设置为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num > 0 && num <= n) {
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
}
